package com.mlh.binarytree;

/**
 * @author 缪林辉
 * @date 2024/3/29 10:15
 * @DESCRIPTION
 */

// 给你两棵二叉树： root1 和 root2 。
// 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。
// 你需要将这两棵树合并成一棵新二叉树。合并的规则是：
// 如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；
// 否则，不为 null 的节点将直接作为新二叉树的节点。
// 返回合并后的二叉树。
// 注意: 合并过程必须从两个树的根节点开始。
public class MergeTrees {
    //自己写的，虽然能通过，但是太不优雅了
    //我的也是递归，但会递归没有返回值，导致每层都需要自己去连接节点，比较复杂
    //而且我怕直接用原来的节点会产生问题,全部都新建节点去连接
    public TreeNode method1(TreeNode root1, TreeNode root2) {
        TreeNode newRoot=new TreeNode();
        if(root1==null&&root2==null){
          return null;
        }else if(root1==null&&root2!=null){
            newRoot.val= root2.val;
            recursion(null,root2.left,newRoot,true);
            recursion(null,root2.right,newRoot,false);
        }else if(root1!=null&&root2==null){
            newRoot.val= root1.val;
            recursion(root1.left,null,newRoot,true);
            recursion(root1.right,null,newRoot,false);
        }else{
            newRoot.val= root1.val+root2.val;
            recursion(root1.left,root2.left,newRoot,true);
            recursion(root1.right,root2.right,newRoot,false);
        }
        return newRoot;
    }

    //father是这层递归节点的父节点,left这指明这层递归的节点是父节点的左子节点还是右子节点
    public void recursion(TreeNode root1, TreeNode root2,TreeNode father,boolean left){
        if(root1==null&&root2==null){
            return;
        }
        TreeNode children=new TreeNode();
        if(root1!=null){
            children.val+= root1.val;
        }
        if(root2!=null){
            children.val+= root2.val;
        }
        if(left){
            father.left=children;
        }else{
            father.right=children;
        }
        if(root1!=null&&root2!=null){
            recursion(root1.left,root2.left,children,true);
            recursion(root1.right,root2.right,children,false);
        }else if(root1==null&&root2!=null){
            recursion(null,root2.left,children,true);
            recursion(null,root2.right,children,false);
        }else{
            recursion(root1.left,null,children,true);
            recursion(root1.right,null,children,false);
        }
    }

    //力扣解法，要返回合并节点，这层要做自己的判断，下一层提供了已合并的节点（左神方法）
    public TreeNode method2(TreeNode root1, TreeNode root2) {
        //这边直接返回，后面都不用走了，因为当前节点为null,说明更没有子节点，直接接上不为null的后面的也都ok了
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        //两边都有构造新节点
        TreeNode merged = new TreeNode(root1.val + root2.val);
        merged.left = method2(root1 .left, root2.left);
        merged.right = method2(root1.right, root2.right);
        return merged;
    }

}
